package leetcode;

import java.util.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-31 19:30
 **/
public class LeetCode394 {

    public static void main(String[] args) {
        LeetCode394 code = new LeetCode394();
        System.out.println(code.decodeString("3[a]2[bc]"));
    }

    int ptr;

    public String decodeString(String s) {
        ptr = 0;
        return getString(s);
    }

    String getString(String s) {
        //当ptr越界或者遇到']'时返回
        if (s.length() == ptr || s.charAt(ptr) == ']') {
            return "";
        }

        StringBuilder builder = new StringBuilder();
        char c = s.charAt(ptr);
        int repeatTime = 0;
        //如果当前字符是数字
        if (Character.isDigit(c)) {
            //获取重复次数
            repeatTime = getDigits(s);
            //移除'['
            ++ptr;
            //递归获取后面的字符串
            String str = getString(s);
            //移除']'
            ++ptr;
            //拼接多次字符串str
            while (repeatTime-- > 0) {
                builder.append(str);
            }
        } else if (Character.isLetter(c)) {
            //是字符直接拼接
            builder.append(c);
            ++ptr;
        }

        //递归拼接
        return builder + getString(s);

    }

    /**
     * 将数字拼接完整
     */
    int getDigits(String s) {
        int res = 0;
        while (ptr < s.length() && Character.isDigit(s.charAt(ptr))) {
            res = res * 10 + s.charAt(ptr++) - '0';
        }
        return res;
    }



    //栈
    /*int ptr;

    public String decodeString(String s) {

        int n = s.length();

        LinkedList<String> stack = new LinkedList<>();

        ptr = 0;
        while (ptr < n) {
            char ch = s.charAt(ptr);
            //分支1,将数字入栈
            //分支2,将字符串和'['入栈
            //分支3,遇到']',将数字和字符出栈
            if (Character.isDigit(ch)) {
                String str = getDigits(s);
                stack.push(str);
            } else if (Character.isLetter(ch) || '[' == ch) {
                stack.push(String.valueOf(ch));
                ++ptr;
            } else {
                ++ptr;

                List<String> list = new LinkedList<>();
                while (!"[".equals(stack.peek())) {
                    list.add(stack.pop());
                }

                //将元素反转,因为弹出的元素顺序是反的
                Collections.reverse(list);

                //移除'['
                stack.pop();

                //弹出数字
                int num = Integer.parseInt(stack.pop());

                //将list中所有字符串拼接成完整的字符串
                String str = getString(list);

                StringBuilder builder = new StringBuilder();
                //添加字符串num次
                while (num-- > 0) {
                    builder.append(str);
                }

                //将拼接多次的字符串入栈
                stack.push(builder.toString());
            }
        }
        return getString(stack);
    }

    *//**
     * 将一个集合中的所有字符拼接成一个整的字符串
     *//*
    String getString(List<String> list) {
        StringBuilder builder = new StringBuilder();
        for (String s : list) {
            builder.append(s);
        }

        return builder.toString();
    }

    *//**
     * 获取数字
     *//*
    String getDigits(String s) {
        StringBuilder builder = new StringBuilder();
        while (Character.isDigit(s.charAt(ptr))) {
            builder.append(s.charAt(ptr++));
        }
        return builder.toString();
    }*/

}
